package prefixTree;

/**
 *  题目 ：单词之和
 *  题目详述 ：
 *  实现一个 MapSum 类，支持两个方法，insert和sum：
 * （1）MapSum() 初始化 MapSum 对象；
 * （2）void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。
 * 如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
 * （3）int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
 *
 */
public class MapSum {
    /**
     * 核心思想 ：
     * （1）使用前缀树来存储字符串，同时将字符串的最后一个字符所对应的前缀树节点中的value属性置为传入的val；
     * （2）sum函数（用于返回以prefix前缀开头的单词的value总和） ：
     *  a.遍历字符串prefix，若是prefix中有字符不存在于前缀树的话，则直接返回不存在；
     *  b.若是prefix中没有字符存在于前缀树的话，
     *  ===》 即直接去遍历（prefix中最后一个字符所对应的前缀树节点）的所有子节点，同时将遍历的子节点的value累加即可；
     */
    TrieNode root;
    // 前缀树节点的数据结构（子节点数组 + 每个节点所保存的值）
    static class TrieNode{
        TrieNode[] children;
        int value;

        public TrieNode(){
            children = new TrieNode[26];
        }
    }

    // 初始化
    public MapSum() {
        root = new TrieNode();
    }

    // 传入字符串和相对应的整数值，来将对应字符串存储进前缀树中
    public void insert(String key, int val) {
        TrieNode node = root;
        for (char c : key.toCharArray()) {
            if(node.children[c - 'a'] == null){
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        // 给每个字符串中最后一个字符所对应的前缀树节点中属性value，置为所传入的值val；
        node.value = val;
    }

    // sum函数 ：即，获取前缀树中以传入字符串prefix为前缀的单词，获取所有单词的值累加值；
    public int sum(String prefix) {
        TrieNode node = root;
        // 遍历前缀字符串，若是遇到前缀树中不存在的字符，说明前缀树中不存在以当前字符串prefix为前缀的单词；
        // 同时，若是前缀树中包含此prefix中的所有字符的话，则应该将prefix字符串中最后一个字符对应的前缀树节点下的所有子节点值进行累加，获取最终结果；
        for (char c : prefix.toCharArray()) {
            if(node.children[c - 'a'] == null){
                return 0;
            }
            node = node.children[c - 'a'];
        }
        // 上述遍历完成之后，即node节点就已经指向prefix字符串中最后一个字符所对应的前缀树节点；
        // 只需要遍历当前前缀树节点的所有子节点即可，同时将所有子节点的值进行累加；
        return sumResult(node);
    }
//    int number = 0;
    // sumResult函数，用来累加当前节点下的所有子节点值 ===》 最终结果result
    private int sumResult(TrieNode node) {
        // 前缀树叶节点的子节点为null，
        // 由于使用了 for (TrieNode child : node.children)，来进行遍历；
        // 不会跳过子数组children中值为null的情况，需要手动进行判断当前遍历的节点是否为空
        if (node == null){
            return 0;
        }
        // 即，初始化result节点，来获取当前节点的值；
        int result = node.value;
        // 对于当前node节点的所有子节点进行遍历
        /**
         *  需要注意的是：
         *  for (TrieNode child : node.children)函数 :
         *  无论node节点子数组中是否为null，都会遍历整个children[26]数组;
         */
        for (TrieNode child : node.children) {
            // 递归遍历（会去遍历当前节点chilren子节点数组中的所有子节点）
            // 继续遍历 node节点中某个子节点的chilren子节点数组，直至node == null为止；
//            number++;
//            System.out.println(result);
            result += sumResult(child);
        }
//        System.out.println(number);
        // 若是当前节点已经不存在子节点了，需要将当前节点的result值返回给其父节点；
        return result;
    }
    /**
     * 分析 ：
     * 时间复杂度 ：
     * （1）insert函数：时间复杂度O（n）（n，为当前遍历单词的长度）；
     * （2）sum函数：时间复杂度O（n + m）（n，为前缀字符串长度；m，为字符串最后一个字符串所对应的前缀树节点下的所有子节点数量）
     */
}
